package 春招冲刺百题计划;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-04-21
 * Time:16:53
 */

/**
 * 春招冲刺百题计划:402. 移掉 K 位数字
 * 中等
 * 相关标签
 * 相关企业
 * 给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
 * 示例 1 ：
 * 输入：num = "1432219", k = 3
 * 输出："1219"
 * 解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。
 */
public class removeKdigits {
    public static void main(String[] args) {
        System.out.println(removeKdigits("1432219", 3));
    }
    public static String removeKdigits(String num, int k) {
        //采用字符数组，可以在后面判断后直接覆盖，同StringBuffer的delete一样
        char[] str = num.toCharArray();
        //n 表示字符数组的长度，h 和 t 用于维护一个双端队列，rm 表示已经移除的数字个数。
        int n = str.length, h = 0, t = -1, rm = 0;
        //创建了一个和输入字符串长度相同的字符数组作为双端队列
        char[] dq = new char[n];
        for (char c : str) {
            //用于移除双端队列中比当前字符大的数字，直到满足条件或者队列为空为止。
            while (h <= t && rm < k && c < dq[t]) {
                t--;
                rm++;
            }
            // 将当前字符加入双端队列
            dq[++t] = c;
        }
        // 从双端队列中取出最小的数字组成字符串，并移除开头多余的 0。找到开头的所有0，并将它们替换为空字符串，从而移除开头多余的0。
        String ans = String.valueOf(dq).substring(h, h + n - k).replaceAll("^0+", "");
        return ans.equals("") ? "0" : ans;
    }
}
